#include <iostream>
#include <string.h>
#include <time.h>
int fibo(int n);

int fibo(int n)
{
    //dp数组的动态规划从f(1), f(2)自底向上往上推
    //dp[1], dp[2], dp[3], ... dp[n]
    int dp[n+1];
    memset(dp, 0, sizeof(dp));
    dp[1] = 1;
    dp[2] = 1;
    for(int i = 3; i <= n; i++)
        dp[i] = dp[i-2] + dp[i-1];
    return dp[n];
}
int main()
{
    using namespace std;
    int begin = clock();
    cout << fibo(45) << endl;
    int end = clock();
    cout << "using " << end - begin << endl;
    return 0;
}
// 1 1 2 3 5 8 13 21 